import java.io.StringReader;

/**
 * Created by L.jp
 * Description:输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 *
 * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
 *
 * 例如:
 * User: 86189
 * Date: 2022-11-20
 * Time: 23:53
 */
class TreeNode {
     int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}
public class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 递归思想 大问题分解为小问题
        // A, B为空 不符题意
        if(A == null || B == null) return false;
        // dfs(A, B) 当前节点B是否是A的子树，若不是，则同理判断当前节点的孩子节点
        return dfs(A, B) || isSubStructure(A.left, B)
                || isSubStructure(A.right, B);
    }
    public boolean dfs(TreeNode A, TreeNode B){
        // 比较孩子节点时, B可以为空， 例如[1]是[5,1]的子树
        if(B == null) return true;
        // A为空, B不为空 B一定不是A子树
        if(A == null) return false;
        // 若两个节点的值不同 则B不可能是A的子树 相同则比较两个节点的孩子节点是否相同
        return A.val == B.val && dfs(A.left, B.left)
                && dfs(A.right, B.right);
    }
}
